package template.primary;

import com.google.common.primitives.Ints;
import javafx.util.Pair;

import java.util.Arrays;
import java.util.List;
import java.util.function.Predicate;

/**
 * @author ：Sei
 * @date ：Created in 2020/1/4 13:14
 * @description：二分查找
 * @modified By：
 * @version: $
 */
public class BinarySearch {
    /**
     * 通用模板，check指定缩小范围的依据
     * @param arr
     * @param target
     * @param check
     * @return
     */
    public static int binarySearch(int[] arr, int target, Predicate<Pair<Integer, Integer>> check){
        int left = 0, right = arr.length, mid;
        while(left<right){
            mid = left+((right-left)>>1);
            if(check.test(new Pair<>(arr[mid], target))){
                right = mid;
            }
            else{left = mid+1;}
        }
//        Or
//        while(left<right){
//            mid = left+(right-left)+1>>1;
//            if(check.test(new Pair<>(mid, target))){
//                left = mid;
//            }
//            else{right = mid-1;}
//        }
        return left;
    }

    /**
     * 列表形式的二分查找，优点是建立泛型，但是算法比赛中较少使用
     * @param lst
     * @param target
     * @param check
     * @param <T>
     * @return
     */
    public static <T> long binarySearch(List<T> lst, T target, Predicate<Pair<T, T>> check){
        int left = 0, right = lst.size()-1, mid;
        while(left<right){
            mid = left+((right-left)>>1);
            if(check.test(new Pair<>(lst.get(mid), target))){
                right = mid;
            }
            else{left = mid+1;}
        }
        return left;
    }


    public static void main(String[] args) {
        int[] arr =  new int[]{1,2,3,4,4,5,5,6,7,8,9};
        int target = 8;
        List<Integer> list = Ints.asList(arr);
        System.out.println(binarySearch(arr, target, p->p.getKey()>=p.getValue()));
        System.out.println(binarySearch(list, target, p->p.getKey()>=p.getValue()));
    }
}
